package lizhe.dummynode;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class MergeKLists {
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0)
            return null;

        if (lists.length == 1)
            return lists[0];

        ListNode res = lists[0];
        for (int i = 1; i < lists.length; i++) {
            ListNode list = lists[i];

            res = mergeTwoLists(res, list);

        }


        return res;
    }

    public static ListNode mergeKLists2(ListNode[] lists) {

        ListNode res = new ListNode();
        ListNode cur = res;
        while (true) {
            Integer min = null;
            int index = -1;
            for (int i = 0; i < lists.length; i++) {
                ListNode list = lists[i];
                if (list == null)
                    continue;

                if (min == null || list.val < min) {
                    min = list.val;
                    index = i;
                }
            }

            if (index == -1)
                break;

            cur.next = lists[index];
            lists[index] = lists[index].next;
            cur = cur.next;
        }
        return res.next;
    }

    public static ListNode mergeKLists3(ListNode[] lists) {
        Queue<ListNode> q = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
        for (ListNode listNode : lists) {
            q.offer(listNode);
        }

        ListNode res = new ListNode();
        ListNode cur = res;
        while (!q.isEmpty()) {
            ListNode min = q.poll();
            cur.next = min;
            cur = min;
            if (min.next != null) {
                q.offer(min.next);
            }
        }

        return res.next;
    }

    public static ListNode mergeKLists4(ListNode[] lists) {
        //递归两两合并
        if (lists.length == 1)
            return null;

        int k = lists.length;
        while (k > 1) {
            int idx = 0;
            for (int i = 0; i < k; i += 2) {
                if (i == k - 1) {
                    lists[idx++] = lists[i];
                } else {
                    lists[idx++] = MergeTwoLists.mergeTwoLists2(lists[i], lists[i + 1]);
                }
            }
            k = idx;
        }
        return lists[0];
    }

    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null)
            return list2;

        if (list2 == null)
            return list1;

        if (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }

    }

    public static void main(String[] args) {
        //[[1,4,5],[1,3,4],[2,6]]
        ListNode l10 = new ListNode(1);
        ListNode l11 = new ListNode(4);
        l10.next = l11;
        ListNode l12 = new ListNode(5);
        l11.next = l12;
        ListNode l20 = new ListNode(1);
        ListNode l21 = new ListNode(3);
        l20.next = l21;
        ListNode l22 = new ListNode(4);
        l21.next = l22;
        ListNode l30 = new ListNode(2);
        ListNode l31 = new ListNode(6);
        l30.next = l31;
        ListNode[] lists = {l10, l20, l30};
        ListNode listNode = mergeKLists4(lists);
    }

}
